#include "dsl.h"
#include <stdlib.h>
#include "fatal.h"

/* START: fig12_23.txt */
struct SkipNode {
	ElementType Element;
	SkipList Right;
	SkipList Down;
};

static Position Bottom = NULL; /* Needs initialization */
static Position Tail = NULL; /* Needs initialization */

/* Initialization procedure */

SkipList Initialize(void) {
	SkipList L;

	if (Bottom == NULL) {
		Bottom = malloc(sizeof(struct SkipNode));
		if (Bottom == NULL)
			FatalError("Out of space!!!");
		Bottom->Right = Bottom->Down = Bottom;

		Tail = malloc(sizeof(struct SkipNode));
		if (Tail == NULL)
			FatalError("Out of space!!!");
		Tail->Element = Infinity;
		Tail->Right = Tail;
	}

	/* Create the header node */
	L = malloc(sizeof(struct SkipNode));
	if (L == NULL)
		FatalError("Out of space!!!");
	L->Element = Infinity;
	L->Right = Tail;
	L->Down = Bottom;

	return L;
}
/* END */

void Output(ElementType Element) {
	printf("%d\n", Element);
}

/* Memory reclamation is left as an exercise */
/* Hint: Delete from top level to bottom level */
SkipList MakeEmpty(SkipList L) {
	L->Right = Tail;
	L->Down = Bottom;
	return L;
}

/* START: fig12_24.txt */
/* Return Position of node containing Item, */
/* or Bottom if not found */

Position Find(ElementType Item, SkipList L) {
	Position Current = L;

	Bottom->Element = Item;
	while (Item != Current->Element)
		if (Item < Current->Element)
			Current = Current->Down;
		else
			Current = Current->Right;

	return Current;
}
/* END */

Position FindMin(SkipList L) {
	Position Current = L;

	while (Current->Down != Bottom)
		Current = Current->Down;

	return Current;
}

Position FindMax(SkipList L) {
	Position Current = L;

	while (Current->Right->Right != Tail || Current->Down != Bottom) {
		if (Current->Right->Right != Tail)
			Current = Current->Right;
		else
			Current = Current->Down;
	}

	return Current;
}

/* START: fig12_25.txt */
SkipList Insert(ElementType Item, SkipList L) {
	Position Current = L;
	Position NewNode;

	Bottom->Element = Item;
	while (Current != Bottom) {
		while (Item > Current->Element)
			Current = Current->Right;

		/* If gap size is 3 or at bottom level */
		/* and must insert, then promote middle element */
		if (Current->Element > Current->Down->Right->Right->Element) {
			NewNode = malloc(sizeof(struct SkipNode));
			if (NewNode == NULL)
				FatalError("Out of space!!!");
			NewNode->Right = Current->Right;
			NewNode->Down = Current->Down->Right->Right;
			Current->Right = NewNode;
			NewNode->Element = Current->Element;
			Current->Element = Current->Down->Right->Element;
		} else
			Current = Current->Down;
	}

	/* Raise height of DSL if necessary */
	if (L->Right != Tail) {
		NewNode = malloc(sizeof(struct SkipNode));
		if (NewNode == NULL)
			FatalError("Out of space!!!");
		NewNode->Down = L;
		NewNode->Right = Tail;
		NewNode->Element = Infinity;
		L = NewNode;
	}

	return L;
}
/* END */

SkipList Remove(ElementType Item, SkipList L) {
	printf("Remove is unimplemented\n");
	if (Item)
		return L;
	return L;
}

ElementType Retrieve(Position P) {
	return P->Element;
}

